package hyy_2022;

import commons.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 树的最小深度
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 */
public class _0824_111_TreeMinDepth {

    /**
     * 深度优先算法：对于每一个非叶子节点,分别计算左右子树的最小叶子节点深度
     * @param root
     * @return int
     */
    public int minDepthDFS(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        int min = Integer.MAX_VALUE;
        if(root.left != null) {
            min = Math.min(minDepthDFS(root.left),min);
        }
        if(root.right != null) {
            min = Math.min(minDepthDFS(root.right),min);
        }
        return min + 1;
    }


    /**
     * 广度优先算法：遍历整颗树,当找到一个叶子节点时,直接返回这个叶子节点的深度
     * 广度优先算法保证了最先搜索到的叶子节点的深度一定最小
     * @param root
     * @return int
     */
    public int minDepthBFS(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int min = 1;
        while(!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode current = deque.poll();
                if(current.left == null && current.right == null) {
                    return min;
                }
                if(current.left != null) {
                    deque.offer(current.left);
                }
                if(current.right != null) {
                    deque.offer(current.right);
                }
            }
            min ++ ;
        }
        return min;
    }


}
